// 解是对的，超时了

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    let all = [];
    const ret = backTracking(s, all);

    // console.log(`${s} is ${JSON.stringify(ret)}`);
    return ret.length;
};

function backTracking(s, all = []) {
    if (s.length <= 0) {
        return [];
    }

    if (s.length === 1) {
        return s === '0' ? [] : [s];
    }

    let availables = backTracking(s.substring(0, s.length - 1), all);

    let cur_piece = s.substring(s.length - 1);

    let res = [];
    for (let i = 0; i < availables.length; i++) {
        let arr = [].concat(availables[i]);
        // 独立放
        if (cur_piece !== '0') {
            arr.push(cur_piece);
            res.push(arr);
        }

        // 粘合放
        let arr2 = [].concat(availables[i]);
        const last_piece_arr = arr2[arr2.length - 1];

        if (last_piece_arr.length == 1 && last_piece_arr !== '0') {
            const new_val = last_piece_arr + cur_piece;
            if (new_val <= '26') {
                arr2[arr2.length - 1] = new_val;
                res.push(arr2);
            }
        }
    }

    return res;
}
